/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode* lessphead, * lessptail;
    ListNode* graterphead, * graterptail;
    lessphead = (ListNode*)malloc(sizeof(ListNode));
    graterphead = (ListNode*)malloc(sizeof(ListNode));
    lessptail = lessphead;
    graterptail = graterphead;
    ListNode* pcur = head;
    while (pcur)
    {
        if (pcur->val < x)
        {
            lessptail->next = pcur;
            lessptail = lessptail->next;
        }
        else
        {
            graterptail->next = pcur;
            graterptail = graterptail->next;
        }
        pcur = pcur->next;
    }
    graterptail->next = NULL;
    lessptail->next = graterphead->next;
    ListNode* ret = lessphead->next;
    free(lessphead);
    free(graterphead);
    lessphead = graterphead = NULL;
    return ret;
}
